#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
using std::endl;
using std::vector;
using std::pair;
using std::min;
using std::queue;
using std::cout;
typedef pair<int, int> Edge;
typedef long long ll;
// from https://uoj.ac/submission/539218
using std::max;
class Flow {
private:
    // static const int MAXN = 1000000;
    static const int MAXN = 1300;
    int siteNum, clientNum;
    int SOURCE_PORT, TARGET_PORT;
    // int n;
    static const ll inf=1e15;
    int n,dis[MAXN],S,T,cur[MAXN],gap[MAXN<<1],curmx=0;
    ll ex[MAXN];
    struct Edge{
        int to,flow,rev;
        Edge(int a, int b, int c): to(a), flow(b), rev(c){}
    };
    vector<Edge> g[MAXN];
    vector<int> buk[MAXN<<1];
    void link(int x,int y,int z){
        g[x].emplace_back(y,z,(int)g[y].size());
        g[y].emplace_back(x,0,(int)g[x].size()-1);
    }
    bool push(int x){
        for(int &o=cur[x];o<g[x].size();o++){
            auto i=g[x][o];
            int y=i.to;
            if(!i.flow||(x!=S&&dis[x]!=dis[y]+1))
                continue;
            int w=min(ex[x],(ll)i.flow);
            if(y!=S&&y!=T&&!ex[y]){
                buk[dis[y]].push_back(y);
                curmx=max(curmx,dis[y]);
            }
            ex[x]-=w,ex[y]+=w,g[x][o].flow-=w,g[y][i.rev].flow+=w;
            if(!ex[x])return 1;
        }
        return 0;
    }
    void Relabel(int x){
        int mn=1e9;
        for(Edge i:g[x]){
            int y=i.to;
            if(i.flow) 
                mn=min(mn,dis[y]);
        }
        gap[dis[x]]--;
        if(!gap[dis[x]]&&dis[x]<=n){
            for(int i=1;i<=n;i++)
                if(i!=S&&i!=T&&dis[i]>dis[x]&&dis[i]<n+1){
                    gap[dis[i]]--,dis[i]=n+1,gap[dis[i]]++;
                    if(ex[i]){
                        buk[dis[i]].push_back(i);
                        curmx=std::max(curmx,dis[i]);
                    }
                }
        }
        dis[x]=mn+1,gap[dis[x]]++;
        if(ex[x])buk[dis[x]].push_back(x),curmx=max(curmx,dis[x]);
    }
    int getflow(){
        while(curmx>0){
            while(buk[curmx].size()&&!ex[buk[curmx].back()])
                buk[curmx].pop_back();
            if(!buk[curmx].size())
                curmx--;
            else 
                return buk[curmx].back();
        }
        if(curmx<=0)return 0;
        exit(1);
    }
    ll HLPP(){
        for(int i=1;i<=n;i++)
            dis[i]=1e9;
        queue<int> q;
        dis[T]=0,q.push(T),ex[S]=inf;
        while(!q.empty()){
            int x=q.front();
            q.pop();
            for(Edge i:g[x]){
                int y=i.to;
                if(!g[y][i.rev].flow)continue;
                if(dis[y]>dis[x]+1)dis[y]=dis[x]+1,q.push(y);
            }
        }
        if(dis[S]>n)return 0;
        for(int i=1;i<=n;i++){
            if(dis[i]<n)gap[dis[i]]++;
            else if(i!=S)dis[i]=n+1;
            if(i!=S&&i!=T&&ex[i]){
                buk[dis[i]].push_back(i);
                curmx=std::max(curmx,dis[i]);
            }
        }
        dis[S]=n;
        push(S);
        while(true){
            int mxp=getflow();
            if(!mxp)
                return ex[T];
            while(!push(mxp)){
                Relabel(mxp);
                cur[mxp]=0;
            }
        }
        return -1;
    }
    Flow(const Flow&);
    void operator=(const Flow&);
    Flow();
public:
    Flow(int siteNum, int clientNum);
    int getMaxFlow();
    void clear();
    void addEdgeFromSource(int siteID, int cap);
    void addEdge(int siteID, int clientID, int cap);
    void addEdgeToTarget(int clientID, int cap);
    void getSponsors(int clientID, vector<pair<int, int>>& receptor);

};
